It has been estimated that roughly one half of all scientific and technical computing cycles are used to optimize linear equations (also known as “linear programming”). This is a staggering statistic given that this area of industry is not a household phrase. However, linear equations apply to many of the important industrial and economic operations that are performed in the world today. From distributing resources throughout the world, to the operating of power grids, to the trading of securities, linear equations can be used to find optimum solutions under specified constraints. Thus, the optimization of linear functions with linear constraints is extremely important to the efficient operation of the modern world.
As a more detailed example, an industrial plant has limited resources of equipment, labor, and raw materials. Each of these variables plays a role in how much of each product the plant can produce. Furthermore, each resource has an associated cost. The profit of such an industrial plant can be modeled through the use of linear equations. And, those linear equations can be optimized to determine how much of each resource (equipment, labor, and raw materials) should be used to attain the greatest profit for the plant.
Through the years, people have tried to employ computers to try to optimize linear equations. This has met with mixed success. For example, in the rather slow world of optimizing a process for an industrial plant, an optimum solution could eventually be obtained heuristically over time. Depending on the linear equation and constraints, the computer optimization process might have to be re-run several times to handle problems that might occur initially, including having the problem cycle, find a clearly incorrect answer, or changing conditions. Nevertheless, given the relatively slow nature of some industrial plant processes, such a delay would not cause any real practical difficulty since the best solution can be found quickly enough to be economically practical. However, in faster processes that operate in real time it becomes much more important to have a reliable process that is not subject to error and that is potentially fast.
Several different methods have been used in the past to approach the solving of linear programs. The more popular of these are known as the Simplex Algorithm, the Revised Simplex Algorithm, the Stored Inverse form of the Revised Simplex Algorithm (SIRSA), and the Implied Inverse form of the Revised Simplex Algorithm (IIRSA).
Algebraic methods for solving linear programs, including all previous versions of methods that are based on the Simplex Algorithm, involve constructing a sequence of equivalent representations of the original problem until a representation is obtained for which the solution is obvious. If the original linear programming problem is Ax=b these methods proceed by attempting to generate a sequence of equivalent systems A1x=b1, A2x=b2, A3x=b3, . . . , Akx=bk until the solution can be read off in an obvious way from the final system. If the calculations that are performed to generate such a sequence of equivalent systems are exact, this technique produces an exactly correct solution.
However, when implemented on digital computers, the calculations are almost never exact in problems that occur in the real world because of errors inherent in the way computers do these calculations. Therefore, while theoretically sound, these traditional algebraic methods fail to produce precisely equivalent representations of the original system Ax=b in actual computer implementations due to the computer error. As a result, all previous versions of Simplex-like methods implemented by computer produce results which are not actually solutions to the original problem. The results they achieve are (usually) fairly close to an exact solution, but they contain errors which are hard to quantify. In ill-conditioned problems, the answer may even be completely unacceptable because these methods may produce, because of the accumulation of computer errors, an answer that presents an optimal solution when there is not one, or these methods may fail to find an optimal solution when there is one. Moreover, it can be difficult to tell when the answers that these methods produce are defective in one of these ways.
The accumulation of computer errors can be envisioned from the sequence A1x=b1, A2x=b2, A3x=b3, . . . , Akx=bk. This sequence should lead to the optimization of the linear equation system to attain a proposed solution. With the error introduced in each subsequent calculation of A due to computer round-off error, one can appreciate the accumulation of computer error as the processing proceeds to the proposed solution Akx=bk. For example, the computer error in A2 would be propagated to A3 and the computer error in A3 would be propagated to A4. Thus, while an algebraic technique may work exactly when implemented by hand, the introduction of a computer to perform the calculations leads to computer errors.
The proposed solution to such computer errors in the past has been to use numerical analysis techniques to analyze the solution steps and then try to redo the solution with fewer solution steps so as to reduce the accumulated computer error. Essentially, this has been a post-hoc attempt to reduce the accumulated error after a proposed solution is achieved—and it requires re-attempting a solution.
Another type of problem is encountered when dealing with linear equations whose constraints change during the process of trying to optimize the problem or after an optimal solution has been obtained. For example, one could envision that during the trading of mortgage backed securities that the price of the security could change quickly. As a constraint, the change in price would affect the optimization of the solution to the problem. Thus, one would be required to start over from the beginning with the new value for the price. There are many such problems in industry. These problems are known as being inherently dynamic.
There have been many proposals for dealing with changed data in versions of the Simplex Algorithm after a solution has been obtained. This is called post-optimal analysis or sensitivity analysis. Techniques for doing this are invariably ad hoc with the analysis depending subjectively on the actual numbers encountered and the form of the solution. To do more than this involves, in essence, restarting the method again from the beginning after the new data have been inserted.
In addition to the Simplex-like methods, some alternative methods known as interior point methods have evolved that have gained some attention since the publication of the Simplex Algorithm by George Dantzig in 1947. For example, Leonid G. Khachiyan in 1979 proposed an ellipsoidal method. And, in 1984, Narendra Karmarkar introduced an interior point method for solving linear equations. See, for example, U.S. Pat. No. 4,744,028 issued to AT&T in the name of Narendra Karmarkar. Other patents related to linear programming include for example, U.S. Pat. No. 5,136,538 to Karmarkar et al. entitled “Preconditioned Conjugate Gradient System”; U.S. Pat. No. 6,078,938 to Pan et al. entitled “Method and System for Solving Linear Systems”; U.S. Pat. No. 6,694,343 to Forrest et al. entitled “Method for Solving a Large Sparse Triangular System of Linear Equations”; U.S. Pat. No. 6,950,844 to Walster et al. entitled “Method and Apparatus for Solving Systems of Linear Inequalities”; and U.S. Pat. No. 7,065,545 to Quintero-de-la-Garza entitled “Computer Methods of Vector Operation for Reducing Computation Time.”
Nevertheless, problems involved with computer implementations of methods for solving linear equations remain. For example, as outlined above, the accumulation of computer errors causes a problem. As another example, changing conditions in dynamic problems also cause difficulties.
Thus, there is a need for improvement in the current state of affairs.